package com.mlh.doublepointer;


import com.mlh.dp.背包问题.完全背包.完全平方数;

//给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
//找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
//返回容器可以储存的最大水量。
//说明：你不能倾斜容器。
//输入：[1,8,6,2,5,4,8,3,7]
//输出：49
//解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
public class 盛最多水的容器 {
	//看题解写出
	//双指针法
	//两个指针指向的数字中较小值∗指针之间的距离
	//如果我们移动数字较大的那个指针，那么前者「两个指针指向的数字中较小值」不会增加，后者「指针之间的距离」会减小，那么这个乘积会减小。
	//因此，我们移动数字较大的那个指针是不合理的。因此，我们移动 数字较小的那个指针。
	//双指针代表了什么？
	//双指针代表的是 可以作为容器边界的所有位置的范围。
	//在一开始，双指针指向数组的左右边界，表示 数组中所有的位置都可以作为容器的边界，因为我们还没有进行过任何尝试。
	//在这之后，我们每次将 对应的数字较小的那个指针 往 另一个指针 的方向移动一个位置，就表示我们认为 这个指针不可能再作为容器的边界了。

	public int method1(int[] height) {
		int n=height.length-1;
		int left=0,right=n;
		int res=0;
		while(left<right){
			if(height[left]>height[right]){
				res=height[right]*(right-left)>res?height[right]*(right-left):res;
				right--;
			}else{
				res=height[left]*(right-left)>res?height[left]*(right-left):res;
				left++;
			}
		}
		return res;
	}

	public int practice(int[] height) {
		int head=0,tail=height.length-1;
		int res=0;
		while (head<tail){
			res=Math.max(res,Math.min(height[head],height[tail])*(tail-head));
			if(height[head]>height[tail]){
				tail--;
			}else {
				head++;
			}
		}
		return res;
	}

	public int practice2(int[] height) {
		int len=height.length;
		int left=0,right=len-1;
		int res=0;
		while(left<right){
			if(height[left]>height[right]){
				res=Math.max(res,height[right]*(right- left));
				--right;
			}else{
				res=Math.max(res,height[left]*(right- left));
				++left;
			}
		}
		return res;
	}

}
